The Data Encryption Standard (DES) algorithm is a block cipher and specifies a cryptographic algorithm that encrypts, using a key, a 64-bit block of plaintext to a 64-bit block of ciphertext. DES is a symmetric algorithm—i.e., the same algorithm and same key are used to decrypt the 64-bit block of ciphertext back to a 64-bit block of plaintext. DES is described in detail in a book by BRUCE SCHNEIER, APPLIED CRYPTOGRAPHY (1996), incorporated by reference herein.
The goal of DES is to encrypt the data such that every bit of the ciphertext depends on every bit of the data and every bit of the key. DES is intended to achieve, after a number of “rounds”, zero correlation between the ciphertext and the original data or key. DES accomplishes this goal using two basic techniques of cryptography—confusion and diffusion. At the simplest level, diffusion is achieved through numerous permutations and confusion is achieved through XOR operations.
In DES, a 56-bit key is derived from a 64-bit key by omitting every eighth bit (The omitted bits can be used as parity to enhance data integrity). Security in DES relies upon the 56-bit key, which can be any 56-bit number and can be changed at any time. From this 56-bit key, 16 different 48-bit subkeys are created for use in 16 DES rounds. FIG. 1 shows a DES algorithm operating on 64-bit of plaintext 110. As shown in FIG. 1, the DES algorithm consists of an initial permutation (IP) operation 112 and a final permutation (IP−1) operation 120, and 16 rounds of encryption operations 114-1 to 114-16. After IP operation 112, plaintext 110 is divided into 32-bit right portion R0 and 32-bit left portion L0. Thereafter, 16 rounds of an identical operation (including “Function f”, explained below) are applied on permuted plaintext 110 using subkeys K1 through K16 (subkeys are explained in further detail below). IP−1 operation 120 provides ciphertext 122, thereby completing the DES algorithm.
IP operation 112 and IP−1 operation 120 provide no additional security. During IP operation 112, a DES integrated circuit loads a 64-bit datum. IP−1 operation 120 is an inverse operation for IP operation 112. Although IP operation 112 and IP−1 120 can be easily implemented in hardware, these operations cannot be efficiently implemented in software. Hence, due to performance considerations, a software implementation of DES often omits IP operation 112 and IP−1 operation 120. While omitting these operations does not compromise security, this modified DES algorithm deviates from the DES standard.
FIG. 2 shows a DES round in further detail. As shown in FIG. 2, a 56-bit key 210 is divided into two 28-bit key portions 210a and 210b, which are then stored. Then, depending on which of the sixteen rounds is currently being executed, stored key portions 210a and 210b are circularly shifted left by either one or two bits. Forty-eight (48) bits of shifted key portions 210a and 210b are selected in compression permutation operation 212 as the subkey Ki for that round. Simultaneously, a 64-bit block of text from either IP operation 112 (first round), or the previous round (i.e., (i−1)th round) is divided into 32-bit left portion Li−1 and 32-bit right portion Ri−1. Using expansion permutation operation 220, right portion Ri−1 is expanded to 48 bits. Like IP operation 112, expansion permutation operation 220 can be implemented readily in hardware but cannot be efficiently implemented in software. The 48-bit output value of expansion permutation operation 220 is then combined with the 48-bit key Ki using XOR operation 225. The 48-bit result of XOR operation 225 is then processed by 8 substitution box (S-box) operations 222, which results in a 32-bit value 226. 32-bit value 226 is then permuted by a permutation box (P-box) operation 224 to provide a 32-bit value 228. Expansion permutation operation 220, XOR operation 225, S-box substitution operation 222 and P-box permutation 224 together constitute Function f, which is a building block of the DES algorithm. 32-bit output value 228 of Function f is then combined with left portion Li−1 using an XOR operation 227. The result of XOR operation 227 is to be used as right portion Ri in the next round. Right portion Ri−1 is provided as left portion Li in the next round, using a swap operation indicated by reference numeral 230. At the end of the 16th round, right portion R15 of the 15th round becomes the left 32 bits, and right portions R16 becomes the right 32 bits, for IP−1 operation 120.
As the encryption/decryption process of the DES algorithm of FIG. 1 is too computationally demanding for a software implementation on a general purpose microprocessor, the DES algorithm is often implemented by an array of identical special purpose modules outside of the microprocessor. However, several drawbacks are inherent in such an approach. First, partitioning the encryption/decryption tasks between the microprocessor and the special purpose modules is complex, especially since different instruction sets are executed by the microprocessor and the special purpose modules. Second, the total silicon area devoted in the integrated circuit for the special-purpose modules is large and costly. Third, the shear number of special purpose modules on the integrated circuit causes decentralization of data flow.
Due to the complexity of the DES algorithm, especially expansion and permutation operations, a software DES implementation is prohibitively slow.
Therefore, a method for implementing the DES algorithm is needed which (a) does not require special purpose modules, (b) combines all data flow into a unified data path, and (c) executes the DES algorithm quickly and inexpensively.